package fun.coding.leetcode;

import java.util.Arrays;

public class ThreeSumClosest {

	public static void main(String[] args) {
		ThreeSumClosest ins = new ThreeSumClosest();
		int[] test1 = {-1, 2, 1, -4};
		System.out.println(ins.threeSumClosest(test1, 1));
	}
	
	public int threeSumClosest(int[] num, int target) {
		if (num == null || num.length < 3) return target;
		
		Arrays.sort(num);
		int minSum = Integer.MAX_VALUE;
		int minDiff = Integer.MAX_VALUE;
		
		for (int i = 0; i < num.length; i++) {
			int l = i + 1;
			int r = num.length - 1;
			
			while (l < r) {
				int sum = num[l] + num[r] + num[i];
				if (Math.abs(sum - target) < minDiff) {
					minSum = sum;
					minDiff = Math.abs(sum - target);
				}
				
				if (sum == target) {
					return minSum;
				} else if (target - sum < 0) {
					r--;
				} else {
					l++;
				}
			}
		}
		return minSum;
    }
}
